package ru.amse.stroganova.algorythms;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import ru.amse.stroganova.graph.AbstractGraph;
import ru.amse.stroganova.graph.Edge;
import ru.amse.stroganova.graph.Vertex;

/**
 * Presents minimum distances search with Dijkstra algorythm.
 * 
 * @author Dasha Stroganova
 *
 */
public class DijkstraAlgorythm {

	private static final String ERROR_MESSAGE = "Cannot find distances using Dijkstra algorythm - there are edges with negative weight.";

	private boolean hasNegativeWeights;
	
	private final Map<Vertex, Integer> distances;
	
	private final Map<Vertex, Vertex> predesessors;
	
	private final AbstractGraph graph;
	
	/**
	 * Creates new Dijkstra algorythm for the given graph and start vertex.
	 * 
	 * @param graph
	 * @param startVertex
	 */
	public DijkstraAlgorythm(AbstractGraph graph, Vertex startVertex) {
		distances = new HashMap<Vertex, Integer>();
		predesessors = new HashMap<Vertex, Vertex>();
		this.graph = graph;
		BinaryHeap<Vertex, Integer> heap = new BinaryHeap<Vertex, Integer>();
		
		for (Vertex vertex : graph.getVertices()) {
			heap.insert(vertex, Integer.MAX_VALUE);
		}
		
		heap.decreaseKey(startVertex, 0);
		
		executeDijkstra(heap);
	}
	
	private void executeDijkstra(BinaryHeap<Vertex, Integer> heap) {
		Set<Vertex> visitedVertices = new HashSet<Vertex>();
		while (!heap.isEmpty()) {
			Vertex vertex = heap.getMin();
			visitedVertices.add(vertex);
			distances.put(vertex, heap.getKey(vertex));
			if (heap.getKey(vertex) == Integer.MAX_VALUE) {
				while (!heap.isEmpty()) {
					distances.put(heap.extractMin(), Integer.MAX_VALUE);
				}
				break;
			}
			for (Edge edge : vertex.getOutgoingEdges()) {
				if (edge.getWeight() < 0) {
					hasNegativeWeights = true;
					return;
				}
				Vertex opposite = edge.getOppositeVertex(vertex);
				if (!visitedVertices.contains(opposite) && (heap.getKey(vertex) + edge.getWeight() < heap.getKey(opposite))) {
					heap.decreaseKey(opposite, heap.getKey(vertex) + edge.getWeight());
					predesessors.put(opposite, vertex);
				}
			}
			heap.extractMin();
		}
	}
	
	/**
	 * If any errors exist return error message.
	 * 
	 * @return error message if error exists; empty string otherwise
	 */
	public String getErrorMessage() {
		return hasNegativeWeights ? ERROR_MESSAGE : "";
	}

	/**
	 * Return map with distances from start vertex to all others. Throws new {@link IllegalStateException} if there are edges with negative weights.
	 * 
	 * @return the distances
	 */
	public Map<Vertex, Integer> getDistances() {
		if (hasNegativeWeights) {
			throw new IllegalStateException("This graph has negative weights. Dijkstra doesn't work correctly.");
		}
		return distances;
	}

	/**
	 * Checks whether givaen graph had edges with negative weights.
	 * 
	 * @return the hasNegativeWeights
	 */
	public boolean hasNegativeWeights() {
		return hasNegativeWeights;
	}
	
	/**
	 * Returns minimal path to given vertex from start one. If there is no path or vertex equals start one - returns empty List. Throws new {@link IllegalStateException} if there are edges with negative weights.
	 * 
	 * @param vertex
	 * @return minimal path to given vertex
	 */
	public List<Edge> getMinimalPathTo(Vertex vertex) {
		if (hasNegativeWeights()) {
			throw new IllegalStateException("This graph has negative weights. Dijkstra doesn't work correctly.");
		}
		
		List<Edge> path = new ArrayList<Edge>();
		for (Vertex currentVertex = vertex; predesessors.get(currentVertex) != null; currentVertex = predesessors.get(currentVertex)) {
			path.add(graph.getConnectingEdge(predesessors.get(currentVertex), currentVertex));
		}
		
		return path;
	}
	
}
